/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class DeleteandEarn {
	public int deleteAndEarn2(int[] nums) {
		int[] freq = new int[10001];
		for (int i = 0; i < nums.length; i++) {
			freq[nums[i]]++;
		}
		int[] dp = new int[freq.length];
		for (int i = 1; i < dp.length; i++) {
			dp[i] = Math.max(i * freq[i] + (i > 1 ? dp[i - 2] : 0), dp[i - 1]);// 也是可以的
		}
		return dp[freq.length - 1];
	}

	public int deleteAndEarn(int[] nums) {
		int[] freq = new int[10001];
		for (int i = 0; i < nums.length; i++) {
			freq[nums[i]]++;
		}
		int res = 0;
		for (int i = 1; i < freq.length;) {
			if (freq[i] == 0) {
				i++;
				continue;
			}
			int j = i;
			while (j < freq.length && freq[j] != 0) {
				j++;
			}
			// 从i到j)是连续值
			int tmp1 = 0, tmp2 = 0;
			int start = i;
			for (; start <= j; start += 2) {
				tmp1 += start * freq[start];
			}
			start = i + 1;
			for (; start <= j; start += 2) {
				tmp2 += start * freq[start];
			}
			res += Math.max(tmp1, tmp2);
			i = j + 1;
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] nums = { 10, 8, 4, 2, 1, 3, 4, 8, 2, 9, 10, 4, 8, 5, 9, 1, 5, 1, 6, 8, 1, 1, 6, 7, 8, 9, 1, 7, 6, 8, 4, 5,
				4, 1, 5, 9, 8, 6, 10, 6, 4, 3, 8, 4, 10, 8, 8, 10, 6, 4, 4, 4, 9, 6, 9, 10, 7, 1, 5, 3, 4, 4, 8, 1, 1,
				2, 1, 4, 1, 1, 4, 9, 4, 7, 1, 5, 1, 10, 3, 5, 10, 3, 10, 2, 1, 10, 4, 1, 1, 4, 1, 2, 10, 9, 7, 10, 1, 2,
				7, 5 };// { 2, 3, 4 };// { 2, 2, 3, 3, 3, 4 };
		System.out.println(new DeleteandEarn().deleteAndEarn(nums));
	}

}
